Traffic management over a high-speed backplane fabric is necessary to insure efficient utilization of available bandwidth. Typically, a backplane fabric interconnects a number of “boards” within a chassis, and a switch coupled with the backplane fabric performs packet switching amongst the boards. The backplane fabric includes a plurality of links that couple each board with the switch, and a failure to efficiently manage the bandwidth over these links may result in packet loss and/or a high latency for communications between boards.
One problem plaguing high-speed backplane fabrics is known as “head-of-line blocking.” As noted above, a switch coupled with the backplane fabric performs packet switching between boards. This switch will include a number of input ports and a number of output ports (usually an equal number), and each board coupled with the backplane is connected with one of these input ports and one of the output ports. Generally, packets (or frames, cells, etc.) arriving at an input port of the switch are, prior to being routed to the appropriate output port, stored in a FIFO (first-in, first-out) buffer or other memory, this memory usually referred to as an “input buffer.” Once a packet has been routed to the appropriate output port, it may again be stored in a FIFO type memory prior to transmission on the output port, this memory usually referred to as an “output buffer.” Often times, the first packet in the output buffer is blocked because that buffer's corresponding output port is busy or congested. When this first packet does not have access to the resource (i.e. output port) that it needs, other packets stored in the output buffer are also blocked. Further, any of the input buffers at the input ports that contain a packet destined for the busy port are also blocked, as the first packet in an input buffer can not be transmitted to the full output buffer. In other words, communications from a number of sources may be blocked due to a “traffic jam” at one port, this condition being referred to as head-of-line blocking.
One way of compensating for head-of-line blocking is to employ a speed-up factor on the fabric links that couple the switch with the boards. If multiple sources are attempting to transmit data to the same destination board, the output port on the switch that is coupled with the destination board will experience heavy traffic. For example, at some instant in time, three boards—e.g., boards A, B, and C—are transmitting data to the same board—e.g., board D—and the switch's output port corresponding to board D may experience traffic that, at that instant in time, is three times the normal I/O bandwidth capacity of the boards. If the bandwidth of the link coupling board D to its corresponding output port on the switch merely equals the board I/O bandwidth capacity, then it may take three times as long for the data to travel from the output buffer (of the switch output port corresponding to board D) to board D. To overcome this latency, a speed-up factor is employed on the fabric links that are coupled with the output ports of the switch. Specifically, additional links may be provided between a board (e.g., board D) and its corresponding output port on the switch, such that the bandwidth of the links is sufficient to handle the increased traffic that may occur when multiple boards (e.g., boards A, B, and C) attempt to communicate with the same destination (e.g., board D).
Ideally, the speed up factor is equal to the number of boards connected to the backplane fabric minus one (i.e., N−1, where N is the number of boards), such that one board may receive traffic from all other boards simultaneously. Accordingly, the link rate equals the board bandwidth capacity multiplied by the speed-up factor, or (N−1). However, such a speed-up factor (i.e., N−1) is impractical where there is even a modest number of boards and, typically, a speed-up factor in the range of 1.5 to 2.5 has proved suitable for most applications. Thus, the speed-up factor helps to minimize head-of-line blocking by more quickly moving data out of the output buffer of each output port on the switch. However, there are limits on the extent to which employing a speed-up factor can control the problem of head-of-line blocking. For example, there are practical limitations on the magnitude of the speed-up factor, as noted above, and, further, increasing the link bandwidth capacity generally increases costs.
The above-described solution—i.e., a speed-up factor—for solving the problems of congestion and head-of-line blocking is not available for all technologies. In particular, the primary standardized switching technologies—e.g., InfiniBand, PCI Express, RapidIO, and Fast Ethernet—are not capable of supporting such a speed-up factor. See, e.g., InfiniBand Architecture Specification, Volumes 1 & 2, Release 1.0.a, June 2001; Peripheral Component Interconnect (PCI) Express Specification, Rev. 1.0 (formerly known as Third Generation I/O, or 3GIO); RapidIO Interconnect Specification, Rev. 1.1, March 2001; and the Institute of Electrical and Electronics Engineers (IEEE) 802.3 family of specifications (Ethernet).